# LeetCode 88、合并两个有序数组
# 一、题目描述
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。
# 二、题目解析
设置两个索引 i 和 j 分别指向 nums1 和 nums2 的有效元素的尾部，从它们的尾部开始向前遍历，同时设置索引 cur 指向 nums1 的最末尾，在每次遍历过程中，比较 i 和 j 指向的元素值大小，把大的元素填充到 cur 的位置，填充完毕说明那个元素已经放置在它应该放置的位置，不需要在管它了，把 cur 向前移动，同时把 i 或者 j 向前移动，继续比较 i 和 j 指向的元素值大小，把大的元素填充到 cur 的位置。
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com/555.html
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 合并两个有序数组( LeetCode 88 ):https://leetcode-cn.com/problems/merge-sorted-array/
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 索引从有序数组 nums1 有效元素的末端开始
// 数组的下标索引从零开始计数
// 索引 0 1 2
// 数组 [ 1 , 2 , 3 ]
int i = m - 1;
// 索引从有序数组 nums2 的末端开始
int j = n - 1;
// 从有序数组 nums1 最末端的位置开始保存元素
int cur = nums1.length - 1;
// 通过循环把 num2 的元素都移动到 num1 中
while( j >= 0 ){
// 比较 num1 和 num2 中当前的元素大小
// 如果 num1 中的索引位置为 i 的元素大于 num2 中索引位置为 j 的元素
// 为了防止越界 i 必须是大于等于 0
if( i >=0 && nums1[i] > nums2[j] ){
// 把 num1 中的索引位置为 i 的元素复制到索引为 cur 的位置
// 此时 cur 的元素已经确定下来
nums1[cur] = nums1[i];
// 接下来去确定 cur 前面一个元素应该放什么数字
cur--;
// 此时，索引 i 需要向前移动
i--;
// 否则，如果 num1 中的索引位置为 i 的元素小于或者等于 num2 中索引位置为 j 的元素
}else{
// 把 num2 中的索引位置为 j 的元素复制到索引为 cur 的位置
nums1[cur] = nums2[j];
// 接下来去确定 cur 前面一个元素应该放什么数字
cur--;
// 此时，索引 j 需要向前移动
j--;
}
}
}
}
# **2、**C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com/555.html
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 合并两个有序数组( LeetCode 88 ):https://leetcode-cn.com/problems/merge-sorted-array/
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
// 索引从有序数组 nums1 有效元素的末端开始
// 数组的下标索引从零开始计数
// 索引 0 1 2
// 数组 [ 1 , 2 , 3 ]
int i = m - 1;
// 索引从有序数组 nums2 的末端开始
int j = n - 1;
// 从有序数组 nums1 最末端的位置开始保存元素
int cur = nums1.size() - 1;
// 通过循环把 num2 的元素都移动到 num1 中
while( j >= 0 ){
// 比较 num1 和 num2 中当前的元素大小
// 如果 num1 中的索引位置为 i 的元素大于 num2 中索引位置为 j 的元素
// 为了防止越界 i 必须是大于等于 0
if( i >=0 && nums1[i] > nums2[j] ){
// 把 num1 中的索引位置为 i 的元素复制到索引为 cur 的位置
// 此时 cur 的元素已经确定下来
nums1[cur] = nums1[i];
// 接下来去确定 cur 前面一个元素应该放什么数字
cur--;
// 此时，索引 i 需要向前移动
i--;
// 否则，如果 num1 中的索引位置为 i 的元素小于或者等于 num2 中索引位置为 j 的元素
}else{
// 把 num2 中的索引位置为 j 的元素复制到索引为 cur 的位置
nums1[cur] = nums2[j];
// 接下来去确定 cur 前面一个元素应该放什么数字
cur--;
// 此时，索引 j 需要向前移动
j--;
}
}
}
};
# 3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https:#www.algomooc.com/555.html
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 合并两个有序数组( LeetCode 88 ):https:#leetcode-cn.com/problems/merge-sorted-array/
class Solution :
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
# 索引从有序数组 nums1 有效元素的末端开始
# 数组的下标索引从零开始计数
# 索引 0 1 2
# 数组 [ 1 , 2 , 3 ]
i = m - 1
# 索引从有序数组 nums2 的末端开始
j = n - 1
# 从有序数组 nums1 最末端的位置开始保存元素
cur = m + n - 1
# 通过循环把 num2 的元素都移动到 num1 中
while j >= 0 :
# 比较 num1 和 num2 中当前的元素大小
# 如果 num1 中的索引位置为 i 的元素大于 num2 中索引位置为 j 的元素
# 为了防止越界 i 必须是大于等于 0
if i >=0 and nums1[i] > nums2[j]:
# 把 num1 中的索引位置为 i 的元素复制到索引为 cur 的位置
# 此时 cur 的元素已经确定下来
nums1[cur] = nums1[i]
# 接下来去确定 cur 前面一个元素应该放什么数字
cur-=1
# 此时，索引 i 需要向前移动
i-=1
# 否则，如果 num1 中的索引位置为 i 的元素小于或者等于 num2 中索引位置为 j 的元素
else:
# 把 num2 中的索引位置为 j 的元素复制到索引为 cur 的位置
nums1[cur] = nums2[j]
# 接下来去确定 cur 前面一个元素应该放什么数字
cur-=1
# 此时，索引 j 需要向前移动
j-=1
# 四、复杂度分析
时间复杂度：O(m+n)。指针移动单调递增，最多移动 m+n 次，因此时间复杂度为 O(m+n)。
空间复杂度：O(m+n)。